\documentclass[11pt]{article}
\usepackage{smallhead}
\usepackage{fullpage}
%\usepackage{times}
%\addtolength{\textwidth}{1.4in}
%\addtolength{\oddsidemargin}{-0.7in}
%\addtolength{\evensidemargin}{-0.7in}
%\addtolength{\topmargin}{-0.8in}
%\addtolength{\textheight}{1.2in}

\usepackage{latexsym,amsmath,amssymb}



\begin{document}

\input{macros}


\vspace{-0.5in}
\begin{center}
{\bf \Large Collaborative Research: The Role of Space and Time in Contagion}
%\bigskip

\end{center}

%\vspace{-0.1in}

\BfPara{Intellectual Merit} 
Diffusion processes defined on networks are general models used in a
number of applications, such as (i) disease transmission in human
contact networks, or (ii) among livestock in farm networks, (iii) spread of
malware in communication networks, and (iv) spread of information, fads and
viral marketing.  Despite the diversity among these applications,
there are fundamental similarities in the mathematical models and
questions of interest, such as understanding the dynamics, and
designing interventions to control the dynamics.  These interventions
often translate to voluntary directives from government or public
agencies; however, people do not always adhere to such
recommendations, and make individual decisions based on their local
network structure, specific utilities and objectives.  Additionally,
people alter their contacts dynamically, and these behavioral changes
have a huge impact on the effectiveness of these interventions.
In this project, we focus on the impact of intervention strategies 
on the spread of contagion.

\noindent {\bf Space: the network as the battleground.}  By space we
mean the network structure at both the local and global scales. Different
strategic agents (e.g., diseases, viruses) have
always been cognizant (implicitly or explicitly) of the underlying
networks and have in fact evolved schemes to modify and exploit
the network structure to their benefit. We propose models that capture
the complexity of interactions and patterns of information exchange found
in the real world including the possibility of vaccine failure and the
potential for moral hazard. In preliminary work we have shown that our models 
can elucidate the mechanism for the counterintuitive, yet real, effect that 
in some situations less vaccination is more effective in the case of HIV.   
%\smallskip

\noindent {\bf Time: a tool of strategy.}  The decision of when to adopt
an interventional strategy or exercise a behavioral choice can play a
crucial role in the spread or containment of a contagion. We will 
consider models where individuals adopt oblivious strategies based on 
Bayesian priors. In preliminary work we have shown that such decision making
in conjunction with the network structure can lead to erratic vaccination
behavior in the case of H1N1 (influenza). We also consider adaptive
strategies where the individual may acquire greater and more accurate information
over time leading to more effective decision-making. \junk{Our results are
consistent with other models showing the increased benefits of adaptive
vaccination for H1N1.}

%\smallskip
We propose a methodological framework for studying the spread and
control of contagions that integrates three key ingredients:
percolation theory, widely used in epidemiology and dynamical systems;
algorithmic game theory for modeling individual decision-making and
studying resulting equilibria; tools from complex networks to model
and analyze social contacts.  Specific questions include: How is the
structure of the network affected by the interplay between the
strategic agents? How can we control the dynamics and evolution of the
complex network in order to achieve a more favorable societal outcome?
Under what conditions do equilibria exist for these intervention
games?  What is the complexity of finding these equilibria?  What is
the structure of mixed equilibria: are they robust to perturbations,
unique, how do they compare to the social optimum?

\BfPara{Broader Impacts} This project will bring together approaches
from Computer Science, Economics, Mathematics, and Epidemiology and
give intellectual unity to the study of contagion.  Our end goal is to
analyze and guide public health policy decisions.  This project
provides the potential for strong dissertation work in computational
epidemiology and algorithmic game theory, and challenging
simulation-based experimental work.  The PIs have introduced several
advanced courses that incorporate concepts from computational
epidemiology, game theory, and network algorithms, all of which are
tied to this project's research aspirations.  An important integrated
activity is the design of course projects modeling real-world
scenarios.

\BfPara{Keywords:} Computational Epidemiology, Algorithms, Game-theory, 
Equilibrium, Simulations


\end{document}




\junk{

 Algorithmic game theory is of
particular relevance to us in this project because we propose going
beyond descriptions and principles of formation; our goal is to
suggest prescriptive policies that will impact the complex network in
ways that improve the human condition.

The local interests and
constraints of the individual players are reflected in the dynamics
and global structure of the resulting complex systems.  These
interests and constraints affect the evolution of the network as well
as the equilibria it tends towards.

Naturally a policy whose
actions or consequences are not efficiently computable has little
meaning and this is why the tools and techniques of algorithmic game
theory are a great match for pursuing this program.

The goal of this project is to study the impact of information and
interaction on the spread and control of contagions.  A contagion
spreads through ``interactions'' in a contact network whose properties
have a significant impact on the extent and dynamics of the spread.
We plan to consider random graph models, as well as
application-specific models such as human contact networks for
epidemiology, farm networks that take into account movement of animals
or farm equipment, and communication networks~\cite{Ne03, EG+04}.
Contagions are often controlled by a variety of interventions, e.g.,
vaccination, quarantining, anti-virus software, etc.  Individual
intervention decisions are based on ``information'' about a variety of
factors such as the cost and perceived efficacy of the intervention,
the current rate of infection and extent of intervention. Individuals
alter their behavior in significant and sometimes unconscious ways,
during the course of an epidemic -- people might reduce avoidable
contacts depending on the perceived risk of infection (e.g., as in the
case of H1N1), or, sometimes increase their contacts after getting
vaccinated (based on overestimation of the efficacy of vaccines),
thereby altering the underlying ``interactions''.  The complex
\emph{interactions} and \emph{information} exchange patterns often
lead to unexpected effects.  For instance, risky behavior in the form
of increased contacts by people who get vaccinated by a vaccine with
limited efficacy could lead to the following perverse outcome: as more
people are vaccinated, the expected outbreak size \emph{increases},
instead of going down; this has been observed in the case of HIV
\cite{blower+risk94}.



Our framework will extend the formulation in Topic 1 to a game
theoretical setting, in which individuals decide on interventions
based on perceived utility.  We will consider utility functions that
take into account limited information available to most individuals,
e.g., the extent of the current outbreak and intervention decisions
(e.g., from nodes within a $d$-neighborhood, or estimates of the
overall outbreak).  We will also consider, when appropriate, the
competing interests of the agents (e.g., among live-stock owners and
department of agriculture in the case of spread of animal diseases).
The main goal is to understand the structure of equilibria in such
non-cooperative games, and the impact of various parameters on their
structure and efficiency.

\item
We plan to consider hybrid models where a subset or subgroup of the
individuals are given preference, while the remaining population makes
individual decisions based on perceived utility.  The study of such
Stackelberg equilibria and their properties will yield guidelines for
prioritizing interventions.

\item
We will develop game-theoretic models that consider the time-evolving
nature of the problem.  For instance, the decision of an individual may depend
not only on extent of the current outbreak, but also on the efficacy
of vaccinations in thwarting outbreaks of previous years.
\end{itemize}
In preliminary work, we have analyzed simple
game-theoretic models that apply both to anti-virus software
installations and vaccinations.  We have found that the amount of
information used in the individual utility function has significant
consequences on the existence and structure of equilibria.
We have investigated how the decisions based on past
epidemic sizes can combine with contact network structure and lead to
erratic flu vaccination behavior.

\end{itemize}

We propose a methodological framework for studying the spread and
control of contagions that integrates three key ingredients:
percolation theory, widely used in epidemiology and dynamical systems;
algorithmic game theory for modeling individual decision-making and
studying resulting equilibria; tools from complex networks to model
and analyze social contacts.  Our research brings together a range of
issues and techniques from computer science, economics and sociology,
making it a good fit for the NSF ICES program solicitation.


Our proposed research has immediate
  consequences for the stability of Internet routing and the
  structures that emerge in overlay, social, and peer-to-peer
  networks.  Our \PPAD\ compendium should serve as an important
  community reference.  But, over the long term, the greater benefit
  of this project will be in creating engineers and mathematicians,
  trained at the intersection of computer science and game theory, who
  are prepared to deal with the complex systems of tomorrow.
}
